Mid Semester Exam

DR. BABASAHEB AMBEDKAR TECHNOLOGICAL UNIVERSITY, LONERE

Course: B. Tech in Information Technology Sem: IV

Subject Name: Data Structures and Applications Subject Code: 24UD1246PC401

Max Marks: 20 Duration: 1 Hr.

Instructions to the Students:

Read the instructions carefully.
Illustrate your answers with neat sketches, diagrams etc. wherever necessary.
Necessary data is given in the respective questions. If such data is not given, it means that the knowledge of that part is a part of the examination.

Q.1 (6 Marks)

#	Question	Options	CO	Marks
1	Why are data structures important in programming?	a) To perform operations like arithmetic calculations b) To organize data efficiently for easier access and modification c) To write syntactically correct code d) To create user interfaces	CO1	1
2	In which data structure is Last In First Out (LIFO) order used?	a) Queue b) Tree c) Stack d) Graph	CO2	1
3	Select the data structure used in evaluation of postfix expression:	a) Stack b) Array c) Linked List d) Queue	CO1	1
4	What does Theta (Θ) notation represent?	a) Upper bound b) Lower bound c) Both upper and lower bound (tight bound) d) Amortized bound	CO1	1
5	What is the worst-case time complexity of linear search?	a) O(1) b) O(log n) c) O(n) d) O(n²)	CO2	1
6	In a singly linked list, each node contains:	a) Data and two pointers b) Only data c) Data and one pointer d) Data and no pointer	CO2	1

Q.2 Solve Any Two of the Following (3 × 2 = 6 Marks)

(A) Define asymptotic notations. Why are they used in algorithm analysis? (CO1)
(B) Explain each step of POP operation using the linked list. (CO2)
(C) How do data structures help in optimizing the performance of algorithms? (CO1)

Q.3 Solve Any One of the Following (8 Marks)

(A) Explain the steps how an infix expression can be converted to a prefix expression using stack and convert the given infix expression (A+(B*C)^D) to prefix using stack. (CO2)
(B) Define a linked list. What are the different types of linked lists? Design a procedure which inserts a node NEW at the end of the linked list. (CO2)

*** End ***